\chapter{\\[-2ex] \LARGE \textbf{二维与三维快速傅里叶变换（FFT）算法推导} \\[-2ex]}

\author{李国斌}
\date{2025.08.31}
	
	\begin{abstract}
		快速傅里叶变换（Fast Fourier Transform, FFT）是计算离散傅里叶变换（DFT）的高效算法，将计算复杂度从$O(N^2)$降低到$O(N\log N)$。Cooley-Tukey算法是FFT最著名的实现方式，基于分治策略。本文重点推导如何将一维Cooley-Tukey FFT算法扩展到二维和三维情形。我们将详细阐述行列分解法（Row-Column Decomposition）的核心思想，分析其计算复杂度，并使用\texttt{TikZ}包绘制算法流程图以清晰展示其执行过程。
	\end{abstract}
	
	\section{引言}
	离散傅里叶变换（DFT）是数字信号处理的基石。对于一维序列$x[n]$, $n=0,1,\ldots,N-1$，其DFT定义为：
	\begin{equation}
		X[k] = \sum_{n=0}^{N-1} x[n] \cdot W_N^{kn}, \quad k=0,1,\ldots,N-1
	\end{equation}
	其中$W_N = e^{-i2\pi/N}$为旋转因子。
	
	直接计算DFT需要$O(N^2)$次复数运算。Cooley和Tukey提出的FFT算法通过将DFT分解为 smaller DFTs 的组合，利用旋转因子的周期性和对称性，将复杂度降至$O(N\log N)$。
	
	在实际应用中，如图像处理（二维）、地震勘探和流体动力学模拟（三维），需要计算高维DFT。设二维数据矩阵为$x[m, n]$，尺寸为$M \times N$，其二维DFT定义为：
	\begin{equation}
		X[k, l] = \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} x[m, n] \cdot W_M^{km} W_N^{ln}
	\end{equation}
	类似地，三维DFT定义为：
	\begin{equation}
		X[k, l, p] = \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} \sum_{q=0}^{Q-1} x[m, n, q] \cdot W_M^{km} W_N^{ln} W_Q^{pq}
	\end{equation}
	直接计算高维DFT的复杂度为$O(M^2N^2)$或$O(M^2N^2Q^2)$，难以承受。因此，将一维FFT思想推广至高维至关重要。本文第二节推导二维FFT算法，第三节推导三维FFT算法。
	
	\section{二维FFT算法推导}
	\subsection{行列分解法}
	观察二维DFT定义式，可以发现其可分离性：
	\begin{equation}
		X[k, l] = \sum_{m=0}^{M-1} \left[ \sum_{n=0}^{N-1} x[m, n] \cdot W_N^{ln} \right] \cdot W_M^{km}
	\end{equation}
	内层求和$\sum_{n=0}^{N-1} x[m, n] \cdot W_N^{ln}$是对矩阵$x$的第$m$行做一维$N$点DFT，得到一个中间结果$G[m, l]$。
	外层求和$\sum_{m=0}^{M-1} G[m, l] \cdot W_M^{km}$是对中间矩阵$G$的第$l$列做一维$M$点DFT。
	
	因此，二维FFT算法可以分解为两个步骤：
	\begin{enumerate}
		\item \textbf{行变换：} 对二维数据的每一行做一维$N$点FFT。
		\item \textbf{列变换：} 对第一步结果的每一列做一维$M$点FFT。
	\end{enumerate}
	
	\begin{center}
		\begin{tikzpicture}[node distance=1.5cm, auto, thick,
			proc/.style={rectangle, draw=blue!60, fill=blue!5, very thick, minimum size=15mm, minimum width=4cm, text width=3.8cm, align=center}]
			% Nodes
			\node (input) {\textbf{输入数据} $x[m, n]$ \\ $M \times N$矩阵};
			\node (proc1) [proc, below=of input] {第一步：行变换 \\ 对每一行执行$N$点FFT};
			\node (inter) [below=of proc1] {\textbf{中间结果} $G[m, l]$};
			\node (proc2) [proc, below=of inter] {第二步：列变换 \\ 对每一列执行$M$点FFT};
			\node (output) [below=of proc2] {\textbf{输出频谱} $X[k, l]$};
			
			% Arrows
			\draw[->, >=stealth, line width=1pt] (input) -- (proc1);
			\draw[->, >=stealth, line width=1pt] (proc1) -- (inter);
			\draw[->, >=stealth, line width=1pt] (inter) -- (proc2);
			\draw[->, >=stealth, line width=1pt] (proc2) -- (output);
		\end{tikzpicture}
		\captionof{figure}{二维FFT行列分解算法流程图}
	\end{center}
	
	\subsection{计算复杂度分析}
	\begin{itemize}
		\item 第一步行变换：共$M$行，每行$N$点FFT复杂度为$O(N \log N)$。总复杂度为$O(M \cdot N \log N)$。
		\item 第二步列变换：共$N$列，每列$M$点FFT复杂度为$O(M \log M)$。总复杂度为$O(N \cdot M \log M)$。
		\item \textbf{总复杂度：} $O(MN(\log M + \log N)) = O(MN \log (MN))$。
	\end{itemize}
	与直接计算二维DFT的复杂度$O(M^2N^2)$相比，FFT带来了巨大的效率提升。
	
	\section{三维FFT算法推导}
	\subsection{扩展的行列分解法}
	三维FFT是二维FFT思想的直接扩展。观察三维DFT定义：
	\begin{align*}
		X[k, l, p] &= \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} \sum_{q=0}^{Q-1} x[m, n, q] \cdot W_M^{km} W_N^{ln} W_Q^{pq} \\
		&= \sum_{m=0}^{M-1} W_M^{km} \left[ \sum_{n=0}^{N-1} W_N^{ln} \left( \sum_{q=0}^{Q-1} x[m, n, q] \cdot W_Q^{pq} \right) \right]
	\end{align*}
	这表明计算可以分解为三个连续的步骤，依次对三个维度进行一维FFT：
	\begin{enumerate}
		\item \textbf{第三维变换：} 对三维数据$x[m, n, q]$的每一个$(m, n)$位置上的$Q$点序列（沿$q$轴）做一维FFT。得到中间结果$G_1[m, n, p]$。
		\item \textbf{第二维变换：} 对$G_1[m, n, p]$的每一个$(m, p)$位置上的$N$点序列（沿$n$轴）做一维FFT。得到中间结果$G_2[m, l, p]$。
		\item \textbf{第一维变换：} 对$G_2[m, l, p]$的每一个$(l, p)$位置上的$M$点序列（沿$m$轴）做一维FFT。得到最终结果$X[k, l, p]$。
	\end{enumerate}
	
	步骤顺序可以任意交换，但计算量相同。
	
	\begin{center}
		\begin{tikzpicture}[node distance=1.2cm, auto, thick,
			proc/.style={rectangle, draw=green!60, fill=green!5, very thick, minimum height=12mm, minimum width=3.2cm, text width=3.0cm, align=center}]
			% Nodes
			\node (input) {\textbf{输入数据} $x[m, n, q]$};
			\node (proc1) [proc, below=of input] {Step 1: 对Q维FFT \\ (固定m, n)};
			\node (inter1) [below=of proc1] {$G_1[m, n, p]$};
			\node (proc2) [proc, below=of inter1] {Step 2: 对N维FFT \\ (固定m, p)};
			\node (inter2) [below=of proc2] {$G_2[m, l, p]$};
			\node (proc3) [proc, below=of inter2] {Step 3: 对M维FFT \\ (固定l, p)};
			\node (output) [below=of proc3] {\textbf{输出频谱} $X[k, l, p]$};
			
			% Arrows
			\draw[->, >=stealth, line width=1pt] (input) -- (proc1);
			\draw[->, >=stealth, line width=1pt] (proc1) -- (inter1);
			\draw[->, >=stealth, line width=1pt] (inter1) -- (proc2);
			\draw[->, >=stealth, line width=1pt] (proc2) -- (inter2);
			\draw[->, >=stealth, line width=1pt] (inter2) -- (proc3);
			\draw[->, >=stealth, line width=1pt] (proc3) -- (output);
		\end{tikzpicture}
		\captionof{figure}{三维FFT算法分解流程图}
	\end{center}
	
	\subsection{计算复杂度分析}
	\begin{itemize}
		\item 第一步：共$M \times N$个$Q$点FFT，复杂度为$O(MN \cdot Q \log Q)$。
		\item 第二步：共$M \times Q$个$N$点FFT，复杂度为$O(MQ \cdot N \log N)$。
		\item 第三步：共$N \times Q$个$M$点FFT，复杂度为$O(NQ \cdot M \log M)$。
		\item \textbf{总复杂度：} $O(MNQ(\log M + \log N + \log Q)) = O(MNQ \log (MNQ))$。
	\end{itemize}
	相比直接计算复杂度$O(M^2N^2Q^2)$，FFT的优势更加显著。
	
	\section{结论}
	本文详细推导了基于行列分解思想的二维和三维FFT算法。该算法的核心在于利用高维DFT的可分离性，将其转化为一系列一维FFT的连续计算。推导过程表明，二维FFT算法可分解为先行变换后列变换的两个步骤，三维FFT算法可分解为依次对三个维度进行变换的三个步骤。
	
	复杂度分析证明，该算法将计算复杂度从$O(N^{2d})$($d$为维度)成功降低到$O(N^d \log N^d)$，这是其能够广泛应用于科学计算和工程实践的根本原因。在实际的软件库（如FFTW, Intel MKL）和硬件实现中，往往还结合了内存访问优化、并行计算等高级技术，但本文所阐述的行列分解法是其最基础且最重要的算法框架。
	